package pers.vic.basics.leetcode;

import java.beans.beancontext.BeanContext;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * @description: 84. 柱状图中最大的矩形 {@literal https://leetcode-cn.com/problems/largest-rectangle-in-histogram/}
 * @author Vic.xu
 * @date: 2021/1/22 0022 9:30
 */
public class J0084_H_LargestRectangleArea {
    /*
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
    求在该柱状图中，能够勾勒出来的矩形的最大面积。
     */

    /**
      看了点单调栈的基础， 现在尝试写一下
      比如 [2, 1, 5, 6, 2, 3]
      1.  2先入栈 [0]
      2.  1比2小，故2 不能再扩大面积，2的面积可以确定：2 * 1 = 2； 2出栈， 1入栈  [1]
      3.  5比1 大 入栈，[1,2]
      4. 6 比 5 大 入栈 [1,2,3]
      5. 2比6 小，6出栈， 6 * 1 = 6  [1,2]
      6. 2比5 小，5出栈。 5 * 2 = 10 [1]
      7. 2比1 大,入栈   [1,4]
      8. 3比2 大， 入栈  [1,4,5]
      9. [1,4,5] 下标的元素分别出栈 对应元素[1,2,3]
      10. 3 出栈 ，3*1 = 3
      11. 2出栈    2*2 = 4
      12. 1 出栈，由于已经没有元素了 1*len = 6
      13. 最大面积是 10

     优化：从第9步，开始的思路和在循环中的出栈逻辑一致，如果在数组的开始和结束均新增一个高度为0的哨兵，就能保证在操作的最后的0的时候能完全出栈而无需额外的操作，这个就是哨兵技巧

     */
    /**
     *  自己些的初版
     */
    public static int largestRectangleArea00(int[] heights) {
        heights = new int[]{4,2,0,3,2,5};
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            //当栈中不为空， 且栈顶元素大于当前元素，则把栈顶元素出栈
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]  ) {
                int height = heights[stack.pop()];
                int width = i;
                if (!stack.isEmpty()) {
                    width = i - stack.peek() - 1;
                }
                area = Math.max(area, height * width);
            }
            //入栈 下标
            stack.push(i);
        }
        //栈中剩余元素出栈
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = len ;
            if (!stack.isEmpty()) {
                width = len - stack.peek() - 1;
            }
            area = Math.max(area, height * width);
        }

        return area;
    }
    public static int largestRectangleArea0(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i++) {
            //当当前矩形 高度 小于栈顶  则出栈
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                while (!stack.isEmpty() && heights[stack.peek()] == height) {
                    stack.pop();
                }
                int width = i;
                if (!stack.isEmpty()) {
                    width = i - stack.peek() - 1;
                }
                area = Math.max(area, height * width);
            }
            stack.push(i);
        }
        //把栈中的数据全部出栈
        while (!stack.isEmpty() ) {
            int height = heights[stack.pop()];
            while (!stack.isEmpty() && heights[stack.peek()] == height) {
                stack.pop();
            }

            int width = len;
            if (!stack.isEmpty()) {
                width = len - stack.peek() - 1;
            }
            area = Math.max(area, height * width);
        }

        return area;
    }

    /**
     *  自己些的优化版
     */
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        //通过哨兵 减少相同的语句
        int [] temp = new int [len+2];
        System.arraycopy(heights, 0, temp, 1, len);
        len = len + 2;
        heights = temp;
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i < len; i++) {
            //当栈中不为空， 且栈顶元素大于当前元素，则把栈顶元素出栈
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]  ) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                area = Math.max(area, height * width);
            }
            //入栈 下标
            stack.push(i);
        }

        return area;
    }


    public static int largestRectangleArea3(int[] heights) {
        // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length);

        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
            // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int h = tmp[stack.pop()];
                area = Math.max(area, (i - stack.peek() - 1) * h);
            }
            stack.push(i);
        }

        return area;

    }


    /**
     * 先试一试暴力解法:妥妥的超时了
     */
    public static int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int area = 0;
        for (int i = 0; i < len; i++) {
            int curHeight = heights[i];
            //每一层高度向两边扩散  找到比它大（等于）的举行
            int left = i;
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }
            int right = i;
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }
            //计算当前层最大面积
            area = Math.max(area, curHeight * (right - left + 1));
        }
        return area;
    }

    public static void main(String[] args) {
        //10
        int[] heights = {2, 1, 5, 6, 2, 3};
        heights = new int[]{2,1,2};
        heights = new int[]{0,2,0};
        heights = new int[]{4,2,0,3,2,5};//6
        System.out.println(" largestRectangleArea:" + largestRectangleArea(heights));
        System.out.println(" largestRectangleArea3:" + largestRectangleArea3(heights));
    }
}
